package com.fps.webshop.question.question0100_0199;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import com.fps.webshop.question.question0700_0799.Question704;

/**
 * 167. 两数之和 II - 输入有序数组
 * 
 * 给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，
 * 所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
 * 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
 *  
 * 示例 1：
 * 输入：numbers = [2,7,11,15], target = 9
 * 输出：[1,2]
 * 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 * 
 * 示例 2：
 * 输入：numbers = [2,3,4], target = 6
 * 输出：[1,3]
 * 
 * 示例 3：
 * 输入：numbers = [-1,0], target = -1
 * 输出：[1,2]
 * 
 * 提示：
 * 		2 <= numbers.length <= 3 * 104
 * 		-1000 <= numbers[i] <= 1000
 * 		numbers 按 递增顺序 排列
 * 		-1000 <= target <= 1000
 * 		仅存在一个有效答案
 */
public class Question167 {
	
	
	/**
	 * 第一次提交，双层循环暴力，未考虑数组特点
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		217 ms	38.7 MB	Java	2021/08/25 14:47
	 * 
	 * 执行用时：217 ms, 在所有 Java 提交中击败了7.53%的用户
	 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了45.23%的用户
	 */
	public static int[] twoSum(int[] numbers, int target) {
		for(int i = 0;i<numbers.length-1;i++) {
			for(int j = i+1;j<numbers.length;j++) {
				if(numbers[i]+numbers[j]==target) {
					return new int[] {i+1,j+1};
				}
			}
		}
		return null;
    }
	
	/**
	 * 第二次提交，讨巧，借用之前的二分查找的方法
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		76 ms	39.3 MB	Java	2021/08/25 15:09
	 * 
	 * 执行用时：76 ms, 在所有 Java 提交中击败了13.82%的用户
	 * 内存消耗：39.3 MB, 在所有 Java 提交中击败了5.31%的用户
	 */
	public static int[] twoSum2(int[] numbers, int target) {
		for(int i = 0;i<numbers.length-1;i++) {
			int[] nums = Arrays.copyOfRange(numbers, i+1, numbers.length);
			int result = Question704.search2(nums, target-numbers[i]);
			if(result!=-1) {
				return  new int[] {i+1,result+i+2};
			}
		}
		return null;
    }
	
	
	
	/**
	 * 第三次提交，利用HashMap
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		2 ms	38.7 MB	Java	2021/08/25 15:16
	 * 
	 * 执行用时：2 ms, 在所有 Java 提交中击败了34.70%的用户
	 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了40.05%的用户
	 */
	public static int[] twoSum3(int[] numbers, int target) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i = 0;i<numbers.length;i++) {
			Integer d = map.get(numbers[i]);
			if(d!=null) {
				return  new int[] {d,i+1};
			}
			map.put(target-numbers[i], i+1);
		}
		return null;
    }
	
	/**
	 * 第四次提交，利用双指针，直接遍历数组
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	38.5 MB	Java	2021/08/25 15:20
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38.5 MB, 在所有 Java 提交中击败了73.23%的用户
	 */
	public static int[] twoSum4(int[] numbers, int target) {
		for (int i = 0, j = numbers.length - 1; i < j;) {
            int sum = numbers[i] + numbers[j];
            if (sum == target){
            	return new int[] {i + 1, j + 1};
            }else if (sum > target){
            	j--;
            }else {
            	i++;
            }
        }
        return null;
    }
	
	public static void main(String[] args) {
		int[] theList = new int[] {1,3,4,4};
		 
		int[] anserList = twoSum3(theList,8);
		
		for(int ss : anserList) {
		 	System.out.print(ss+" ");
		 }
	}
}
